• 阐述

  是离散 Fourier 变换的量子版本。

  对于由 $n$ 个量子位构成的向量，其状态数为 $N=2^n$，定义 $N$ 次单位根 $\omega=e^{2\pi i/N}$，则 $n$ 阶张量积态 $|j\rangle$ 的正向变换为

  $$|j\rangle \longrightarrow \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \omega^{j k}|k\rangle=\frac{1}{\sqrt{N}} \bigotimes_{i=1}^{n}\left(|0\rangle+\omega^{2^{n-i}j}|1\rangle\right)$$

  相应的逆向变换为

  $$|k\rangle \longrightarrow \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \omega^{-kj}|j\rangle$$

• 实例

• 性质

• 相关内容

  该变换可以由 Hadamard 门和控制旋转门 $R_n$ 实现，其中

  $$R_{n}=\left(\begin{array}{cc}1 & 0 \\ 0 & e^{2 \pi i / 2^n}\end{array}\right)$$

  注意到 $\omega^{2^{n-i}j}=e^{2\pi i[0.j_{n-i+1}\ldots j_n]}$，我们可以设计出如下电路：

  

  注意，输入和输出的顺序是相反的。

• 参考文献

• Quantum Fourier transform - Wikipedia